⟸ Go Back ⟸
Exercise 3 (Homework 1).
(Kleene star, theory of languages)

Kleene Star – basic properties

Justify your answers to the following questions. Languages are taken over any fixed alphabet.

  1. Does the Kleene star distribute over concatenation of languages? That is, for every two languages L_1,L_2, does it hold that L_1^*L_2^*= (L_1L_2)^*? What if instead of “=” we only asked for “\subseteq” or “\supseteq”? What if we impose L_1=L_2, does it hold now? And what if, when L_1=L_2, instead of “=” we only asked for “\subseteq” or “\supseteq”?
  2. Do positive closures always induce nontrivial partitions? That is, for every two languages L_1,L_2, if L_1^+\cup L_2^+=\{a,b\}^+ and L_1^+\cap L_2^+=\emptyset, then either L_1=\emptyset or L_2=\emptyset.
  3. Does the Kleene star distribute over union of languages? That is, for every two languages L_1,L_2, does it hold that L_1^*\cup L_2^*= (L_1\cup L_2)^*? What if instead of “=” we only asked for “\subseteq” or “\supseteq”?
  4. Does the Kleene star distribute over intersection of languages? That is, for every two languages L_1,L_2, does it hold that L_1^*\cap L_2^*= (L_1\cap L_2)^*? What if instead of “=” we only asked for “\subseteq” or “\supseteq”?
  5. Is the Kleene star monotone w.r.t. inclusion? That is, for every two languages L_1,L_2, does L_1\subseteq L_2 imply L_1^*\subseteq L_2^*? Does the converse hold? That is, for every two languages L_1,L_2, does L_1^*\subseteq L_2^* imply L_1\subseteq L_2? What if L_1=\{a,b\} and L_2 is a language over \{a,b\}, does the converse hold in this special context?
  6. Chain of inclusions. Does it hold for every language L that \overline{L^*}\subseteq \overline{L}\subseteq \overline{L}^*? What if we reverse the inclusions? Does \overline{L^*}\supseteq \overline{L}\supseteq \overline{L}^* hold?
  7. Sufficient condition for distinct Kleene stars. Does L_1\cap L_2=\emptyset for two languages L_1, L_2 \not=\emptyset imply L_1^*\not=L_2^*?
  8. Where is the positive closure squared? Does L^+L^+\subseteq L^+ hold for every language L? Does the reverse inclusion L^+L^+\supseteq L^+ hold?